var Tree = function () {
  var Node = function (value) {
    this.value = value;
    this.left = null;
    this.right = null;
  };
  var root = null;

  this.insert = (key) => {
    let newNode = new Node(key);

    if (root === null) {
      root = newNode;
    } else {
      insertNode(root, newNode);
    }
  };

  var insertNode = function (node, newNode) {
    if (node == null) {
      node = newNode;
    } else if (newNode.value < node.value) {
      node.left = insertNode(node.left, newNode);
      if (node.left !== null) {
        if (heightNode(node.left) - heightNode(node.right) > 1) {

          // console.log(newNode)
          // if (newNode.value < node.left.value) {
          //   node = rotationLL(node);
          // } else {
          //   node = rotationLR(node);
          // }
        }
      }
    } else if (newNode.value > node.value) {
      node.right = insertNode(node.right, newNode);
      if (node.right !== null) {
        if (heightNode(node.right) - heightNode(node.left) > 1) {
          // console.log(heightNode(node.right) - heightNode(node.left))
          // if (newNode.value > node.right.value) {
          //   node = rotationRR(node);
          // } else {
          //   node = rotationRL(node);
          // }
        }
      }
    }
    return node;
  };

  var heightNode = function (node) {
    if (node === null) {
      return -1;
    } else {
      return Math.max(heightNode(node.left), heightNode(node.right)) + 1;
    }
  };
  //RR向左的单旋转
  var rotationRR = function (node) {
    var tmp = node.right;
    node.right = tmp.left;
    tmp.left = node;
    return tmp;
  };
  //LL向右的单旋转
  var rotationLL = function (node) {
    var tmp = node.left;
    node.left = tmp.right;
    tmp.right = node;
    return tmp;
  };
  //LR向右的双旋转
  var rotationLR = function (node) {
    node.left = rotationRR(node.left);
    return rotationLL(node);
  };
  //RL向左的双旋转
  var rotationRL = function (node) {
    node.right = rotationLL(node.right);
    return rotationRR(node);
  };

  //显示树
  this.getRoot = function () {
    return root;
  };
};

let tree = new Tree();

tree.insert(11);
tree.insert(7);
tree.insert(15);
tree.insert(5);
console.log(tree.getRoot());

tree.insert(3);
// tree.insert(9);
console.log(tree.getRoot());